import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author lilongkang
 * @version 1.0
 * @description: TODO
 * @date 2024/3/22 9:46
 */
public class PriorityQueueAlgorithm {

    /**
     * 一百万个元素的数组查找最小的10个元素。
     * 思路：维护一个固定大小为10的优先队列，降序排序。
     * 队列顶元素为队列中最大的，和后续的数组元素对比，如果数组元素大于队列顶元素则继续遍历，否则把队列顶元素弹出，数组元素入队列。
     * 这样就能够一直维持一个最小的10个元素。
     * @param args
     */
    public static void main(String[] args) {
        int[] test = new int[]{23, 32, 58, 10, 8, 7, 3, 20, 20, 11, 98, 99};
        int[] minNums = minNums(test);
        int[] minNums2 = priorityQueue(test);

        System.out.println(minNums);
        System.out.println(minNums2);
    }

    public static int[] minNums(int[] source) {
        if (source.length < 10) {
            return new int[]{};
        }
        List<Integer> numsList = new ArrayList<>();
        for (int i = 0; i < source.length; i++) {
            numsList.add(source[i]);
        }
        List<Integer> collect = numsList.stream().sorted(Comparator.comparing(m -> m)).toList();

        int[] result = new int[10];
        for (int i = 0; i < 10; i++) {
            result[i] = collect.get(i);
        }
        return result;
    }

    public static int[] priorityQueue(int[] source) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(10,Comparator.reverseOrder());
        // 建堆
        for (int i = 0; i < 10; i++) {
            priorityQueue.offer(source[i]);
        }
        // 维护优先队列
        for (int i = 10; i < source.length; i++) {
            Integer peek = priorityQueue.peek();
            if (source[i] < peek) {
                priorityQueue.poll();
                priorityQueue.offer(source[i]);
            }
        }
        // 输出结果
        int[] result = new int[10];
        for (int i = 0; i < 10; i++) {
            result[i] = priorityQueue.poll();
        }
        return result;
    }
}
